Optimization and Physics: On the satisfiability of random Boolean formulae

摘要

LECTURE GIVEN AT TH2002. Given a set of Boolean variables, and some constraints between them, is itpossible to find a configuration of the variables which satisfies allconstraints? This problem, which is at the heart of combinatorial optimizationand computational complexity theory, is used as a guide to show the convergencebetween these fields and the statistical physics of disordered systems. Newresults on satisfiability, both on the theoretical and practical side, can beobtained thanks to the use of physics concepts and methods.